package org.example.algorithm.heap;

/**
 * 构建一个大顶堆, 然后从中pop出k-1个元素，则堆顶元素即为第k大元素
 */
public class FindKthLargestUseMaxHeap {

    public int findKthLargest(int[] nums, int k) {
        //最后一个非叶子节点
        int pos = (nums.length - 2) / 2;
        //数组堆化
        for (int i=pos;i>=0;i--) {
            siftDown(nums, i, nums.length);
        }
        for (int i=0;i<k-1;i++) {
            removeMax(nums, nums.length - i);
        }
        return nums[0];
    }

    public int removeMax(int[] arr, int heapSize) {
        int max = arr[0];
        arr[0] = arr[heapSize-1];
        heapSize--;
        siftDown(arr, 0, heapSize);
        return max;
    }

    public void siftDown(int[] arr, int pos, int heapSize) {
        int left = 2 * pos + 1;
        int right = 2 * pos + 2;
        int maxPos = pos;
        if (left <= heapSize-1 && arr[left] > arr[maxPos]) {
            maxPos = left;
        }
        if (right <= heapSize-1 && arr[right] > arr[maxPos]) {
            maxPos = right;
        }
        if (maxPos != pos) {
            swap(arr, maxPos, pos);
            siftDown(arr, maxPos, heapSize);
        }
    }

    public void swap(int[] arr, int from, int to) {
        int temp = arr[from];
        arr[from] = arr[to];
        arr[to] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {-1, 2, 0};
        FindKthLargestUseMaxHeap findHeap = new FindKthLargestUseMaxHeap();
        int res = findHeap.findKthLargest(arr, 3);
        System.out.println(res);
    }
}
